Komputery trzybitowe

Limit pamięci: 32 MB

Naukowcy w Królestwie Bajtlandii postanowili stworzyć nowy rodzaj komputerów, a mianowice komputery trzybitowe (KTB). Powszechnie uważa się, że ten nowy rodzaj komputerów pozwoli rozwiązać wiele problemów zbyt trudnych dla klasycznych komputerów. Niestety, w trakcie prac naukowcy napotkali wiele trudności technicznych. Twoim zadaniem jest pomóc im w przezwyciężeniu jednej z nich.

Naukowcy zajmują się aktualnie procedurami inicjalizacji pamięci komputera. Komputer KTB posiada bitów pamięci ponumerowanych liczbami . Każdy bit może przyjmować jedną z trzech wartości lub być w stanie niezainicjalizowanym. Komputer KTB udostępnia następujące operacje inicjalizujące:

• dwóm kolejnym niezainicjalizowanym bitom można przypisać dwie różne wartości,
• dwóm kolejnym bitom, z których jeden jest niezainicjalizowany, a drugi ma wartość , można przypisać dwie różne wartości, przy czym obie muszą być różne od .

Zadanie

Napisz program, który:

• wczyta wartości, którymi ma być zainicjalizowana pamięć,
• sprawdzi czy taka inicjalizacja jest możliwa,
• wypisze znalezioną odpowiedź.

Wejście

Standardowe wejście może zawierać opisy od do konfiguracji pamięci, które chcemy uzyskać. Pierwszy wiersz wejścia zawiera pojedynczą liczbę całkowitą - liczbę konfiguracji. W kolejnych wierszach znajdują się opisy konfiguracji. Opis jednej konfiguracji składa się z dwóch wierszy. Pierwszy wiersz zawiera pojedynczą liczbę całkowitą , , rozmiar pamięci dla -tej konfiguracji. Drugi wiersz zawiera ciąg długości składający się z liter - ciąg ten opisuje konfigurację, którą chcemy uzyskać.

Wyjście

Standardowe wyjście powinno zawierać wierszy, po jednym dla każdej konfiguracji pamięci. -ty wiersz powinien zawierać pojedyncze słowo TAK, jeśli inicjalizacja jest możliwa, w przeciwnym przypadku NIE.

Przykład

Dla danych wejściowych:

2
4
aaab
4
aabb

poprawną odpowiedzią jest:

TAK
NIE

Zapożyczenie z CPSPC: Piotr Sankowski.